using BepuUtilities;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace BepuPhysics.Trees
{
    partial struct Tree
    {
        unsafe void RemoveNodeAt(int nodeIndex)
        {
            // 请注意,此函数是高速缓存加扰影响。没关系-缓存优化例程稍后会处理它。
            Debug.Assert(nodeIndex < nodeCount && nodeIndex >= 0);
            // 我们在此不保证在删除后保持树的一致性。
            // 那是打电话给RemoveAt的人的责任。
            --nodeCount;
            // 如果该节点不是列表中的最后一个节点,它将被最后一个节点替换。
            if (nodeIndex < nodeCount)
            {
                // 用删除的节点替换最后一个节点。
                ref var node = ref Nodes[nodeIndex];
                node = Nodes[nodeCount];
                ref var metanode = ref Metanodes[nodeIndex];
                metanode = Metanodes[nodeCount];

                // 更新移动的节点的指针：
                // 其父对象的子指针应该更改,并且.
                Unsafe.Add(ref Nodes[metanode.Parent].A, metanode.IndexInParent).Index = nodeIndex;
                // 它的子级的父指针应该改变。
                ref var nodeChildren = ref node.A;
                for (int i = 0; i < 2; ++i)
                {
                    ref var child = ref Unsafe.Add(ref nodeChildren, i);
                    if (child.Index >= 0)
                    {
                        Metanodes[child.Index].Parent = nodeIndex;
                    }
                    else
                    {
                        // 它是一个叶节点。它需要更新它的指针。
                        Leaves[Encode(child.Index)] = new Leaf(nodeIndex, i);
                    }
                }

            }


        }


        unsafe void RefitForRemoval(int nodeIndex)
        {
            // 请注意,不会尝试重新调整根节点。请注意,根节点是唯一可以具有小于2个子节点的节点。
            ref var node = ref Nodes[nodeIndex];
            ref var metanode = ref Metanodes[nodeIndex];
            while (metanode.Parent >= 0)
            {
                // 计算此节点的新边界框。
                ref var parent = ref Nodes[metanode.Parent];
                ref var childInParent = ref Unsafe.Add(ref parent.A, metanode.IndexInParent);
                BoundingBox.CreateMerged(node.A.Min, node.A.Max, node.B.Min, node.B.Max, out childInParent.Min, out childInParent.Max);
                --childInParent.LeafCount;
                node = ref parent;
                metanode = ref Metanodes[metanode.Parent];
            }
        }

        /// <summary>
        /// 删除索引处的叶。如果索引不在叶列表的末尾,则将最后一个叶交换到删除的位置。
        /// </summary>
        /// <param name="leafIndex">要删除的叶的索引。</param>
        /// <return>移动到已删除叶的槽中的叶的以前索引(如果有)。
        /// 如果leafIndex指向列表中的最后一个槽,则返回-1,因为没有移动任何叶。</return>
        public unsafe int RemoveAt(int leafIndex)
        {
            if (leafIndex < 0 || leafIndex >= leafCount)
                throw new ArgumentOutOfRangeException("Leaf index must be a valid index in the tree's leaf array.");

            // 缓存要删除的叶。
            var leaf = Leaves[leafIndex];
            // 从树叶数组中删除树叶。
            --leafCount;
            if (leafIndex < leafCount)
            {
                // 移走的叶子不是最后一片叶子,所以我们应该把最后一片叶子移到它的槽里。
                // 这可能会导致某种形式的高速缓存加扰,但在高性能阶段期间不需要引用这些叶子。
                // 它确实在一定程度上降低了AABB更新的性能,但我们不应该为此费心进行任何形式的缓存优化,除非它成为一个经过验证的问题。
                ref var lastLeaf = ref Leaves[leafCount];
                Leaves[leafIndex] = lastLeaf;
                Unsafe.Add(ref Nodes[lastLeaf.NodeIndex].A, lastLeaf.ChildIndex).Index = Encode(leafIndex);
            }

            ref var node = ref Nodes[leaf.NodeIndex];
            ref var metanode = ref Metanodes[leaf.NodeIndex];
            ref var nodeChildren = ref node.A;

            // 从此节点中删除叶。
            // 请注意,子项必须保持连续。需要获取节点的最后一个子节点并移动到插槽中
            // 如果被带走的孩子不是最后一个孩子。
            // 此外,如果移动子对象并且它是叶,则必须更新该叶的ChildIndex。
            // 如果移动子节点并且它是内部节点,则必须更新该节点的所有直接子节点的父节点。

            var survivingChildIndexInNode = leaf.ChildIndex ^ 1;
            ref var survivingChild = ref Unsafe.Add(ref nodeChildren, survivingChildIndexInNode);

            // 检查此节点是否应该折叠。
            if (metanode.Parent >= 0)
            {
                // 这是一个非根内部节点。
                // 由于节点中只有两个子节点,因此包含移除的叶子的节点将折叠。

                // 将另一个节点移动到用于指向正在折叠的内部节点的插槽中。
                ref var childInParent = ref Unsafe.Add(ref Nodes[metanode.Parent].A, metanode.IndexInParent);
                childInParent.Min = survivingChild.Min;
                childInParent.Max = survivingChild.Max;
                childInParent.Index = survivingChild.Index;
                childInParent.LeafCount = survivingChild.LeafCount;

                if (survivingChild.Index < 0)
                {
                    // 这是一片叶子。更新叶子数组中的叶子引用。
                    var otherLeafIndex = Encode(survivingChild.Index);
                    Leaves[otherLeafIndex] = new Leaf(metanode.Parent, metanode.IndexInParent);
                }
                else
                {
                    // 它是一个内部节点。更新其父节点。
                    ref var survivingMeta = ref Metanodes[survivingChild.Index];
                    survivingMeta.Parent = metanode.Parent;
                    survivingMeta.IndexInParent = metanode.IndexInParent;
                }

                // 向上调整父指针链,重新设置边界框并减少叶数。
                // 请注意,这从父级开始;我们已经通过折叠对当前关卡进行了重新调整。
                RefitForRemoval(metanode.Parent);

                // 删除现在失效的节点。
                RemoveNodeAt(leaf.NodeIndex);


            }
            else
            {
                // 这就是根。它不能折叠,但如果另一个子节点是内部节点,则它将覆盖根节点。
                // 这保持了这样的保证,即任何至少具有2个叶节点的树都有用节点或叶填充的每个单个子槽。
                Debug.Assert(leaf.NodeIndex == 0, "Only the root should have a negative parent, so only the root should show up here.");
                if (leafCount > 0)
                {
                    // 删除后的leavCount仍然是正数,因此根节点中必须至少有一个子节点。
                    // 如果它是内部节点,则它将被提升到根节点的插槽中。
                    if (survivingChild.Index >= 0)
                    {
                        // 幸存的子节点是内部节点,它应该替换根节点。
                        var pulledNodeIndex = survivingChild.Index;
                        // TODO：此节点移动逻辑可以与节点移动的其他实例统一。它是根,这一事实并没有什么特别之处。
                        Nodes[0] = Nodes[pulledNodeIndex]; // 请注意,这会覆盖其他Child引用所指向的内存。
                        Metanodes[0].Parent = -1;
                        Metanodes[0].IndexInParent = -1;
                        // 更新移动的内部节点的子节点的父指针。
                        for (int i = 0; i < 2; ++i)
                        {
                            ref var child = ref Unsafe.Add(ref Nodes[0].A, i);
                            if (child.Index >= 0)
                            {
                                // 子节点是一个内部节点。请注意,Child中的索引没有更改;我们直接复制子对象。
                                Metanodes[child.Index].Parent = 0;
                            }
                            else
                            {
                                // 子节点是一个叶节点。
                                Leaves[Encode(child.Index)] = new Leaf(0, i);
                            }
                        }
                        RemoveNodeAt(pulledNodeIndex);
                    }
                    else
                    {
                        // 幸存的子节点是叶节点。
                        if (survivingChildIndexInNode > 0)
                        {
                            // 需要移动它以保持最低的位置被填满。
                            Nodes[0].A = Nodes[0].B;
                            // 更新叶指针以反映更改。
                            Leaves[Encode(survivingChild.Index)] = new Leaf(0, 0);
                        }
                    }
                }
                // 这里不需要执行RefitForRemoval;它是根。没有更高的边界框。
            }
            return leafIndex < leafCount ? leafCount : -1;
        }
    }
}
